#include <iostream>
#include "minHeap.h"
#include <string>
#include "character.h"
using namespace std;
template <typename T>
class hNode; 
template <typename T>
class Node {
public:
	template <typename T>
	friend class binaryTree;
	Node();
	Node(Node<T>& node);
	Node(T value);
	Node(T value, Node<T>* left, Node<T>* right);
	T& getValue() { return value; }
	Node<T>* getLeft() { return this->leftChild; }
	Node<T>* getRight() { return this->rightChild; }
	void setLeft(Node<T>* left);
	void setRight(Node<T>* right);
	~Node();
	template <typename T>
	friend bool operator>(Node<T>& a, Node<T>& b);
	template <typename T>
	friend bool operator<(Node<T>& a, Node<T>& b);
	template <typename T>
	friend bool operator<=(Node<T>& a, Node<T>& b);
private:
	T value;
	Node<T>* leftChild;
	Node<T>* rightChild;
};
template <typename T>
Node<T>::Node() {
	this->value = 0;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
Node<T>::Node(Node<T>& node) {
    value = node.getValue();
	leftChild = node.getLeft();
	rightChild = node.getRight();
}
template <typename T>
Node<T>::Node(T value) {
	this->value = value;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
Node<T>::~Node() {

}
template <typename T>
Node<T>::Node(T value, Node<T>* left, Node<T>* right) {
	this->value = value;
	leftChild = left;
	rightChild = right;
}
template <typename T>
void Node<T>::setLeft(Node<T>* left) {
	leftChild = left;
}
template <typename T>
void Node<T>::setRight(Node<T>* right) {
	rightChild = right;
}
template <typename T>
bool operator>(Node<T>& a, Node<T>& b) {
	if (a.value > b.value)
		return true;
	else
		return false;
}
template <typename T>
bool operator<(Node<T>& a, Node<T>& b) {
	if (a.value < b.value)
		return true;
	else
		return false;
}
template <typename T>
bool operator<=(Node<T>& a, Node<T>& b) {
	if (a.value <= b.value)
		return true;
	else
		return false;
}
template <typename T>
class binaryTree {
public:
	template <typename T>
	friend class Node;
	binaryTree();
	~binaryTree();
	void makeTree(int x, binaryTree<T>& left, binaryTree<T >& right);
	void inOrderTraverse(Node<T>* root);
	void inverseTraverse(Node<T>* root, ofstream& out, int depth);
	void myTraverse(Node<T>* root, string& str,Character* temp, const int count);
	void codingTraverse(Node<T>* root, Node<T>* tempNode);
	void setRoot(Node<T>* r);
	Node<T>* getRoot();
	void addChild(Node<T>* left, Node<T>* right);
	binaryTree<T>* huffmanTree(T* chGroup, int n);
private:
	Node<T>* root;
};
template <typename T>
binaryTree<T>::binaryTree() {
	root = new Node<T>();
}
template <typename T>
void binaryTree<T>::makeTree(int x, binaryTree<T>& left, binaryTree<T>& right) {
	root->value = x;
	root->leftChild = left.getRoot();
	root->rightChild = right.getRoot();
}
template <typename T>
binaryTree<T>::~binaryTree() {
	delete root;
}
template <typename T>
void binaryTree<T>::addChild(Node<T>* left, Node<T>* right) {
	root->leftChild = left;
	root->rightChild = right;
}
template <typename T>
void binaryTree<T>::setRoot(Node<T>* r) {
	root = r;
}
template <typename T>
Node<T>* binaryTree<T>::getRoot() {
	return root;
}
template <typename T>
void binaryTree<T>::inOrderTraverse(Node<T>* root) {
	if (root == nullptr)return;
	inOrderTraverse(root->leftChild);
	if(root->value.ch!=0)
		cout << root->value << endl;
	inOrderTraverse(root->rightChild);
}

/*template <typename T>
void binaryTree<T>::codingTraverse(Node<T>* root, Node<T>* tempNode) {
	if (root == nullptr)return;
	codingTraverse(root->leftChild, Node<T>* tempNode);
	int i = 0;
	while (1) {
		cout << "while" << endl;
		if (root->value.ch == tempNode[i].value.ch) {
			tempNode[i].value.code = root->value.code;
			break;
		}
		i++;
	}
	codingTraverse(root->rightChild, Node<T>*tempNode);
}*/
template <typename T>
void binaryTree<T>::myTraverse(Node<T>* root,string& str,Character* tempGroup,const int count) {
	if (root == nullptr) return; 
	str += "0";
	myTraverse(root->leftChild, str,tempGroup,count);
	str.erase(str.end() - 1);
	if (root->leftChild == nullptr && root->rightChild == nullptr) {
		root->value.code = str;
		cout << root->value << endl;
		for (int i = 0; i < count; i++) {
			if (root->value.ch == tempGroup[i].ch)
				tempGroup[i].code = root->value.code;
		}
	}
	str += "1";
	myTraverse(root->rightChild, str,tempGroup,count);
	str.erase(str.end() - 1);
}
template <typename T>
void binaryTree<T>::inverseTraverse(Node<T>* root, ofstream& out, int depth) {
	Node<T>* tool = new Node<T>(0, nullptr, nullptr);
	if (root == nullptr)return;
	depth++;
	inverseTraverse(root->rightChild, out, depth);
	for (int i = 1; i < depth; i++)
		out << tool->value << tool->value << tool->value << tool->value << tool->value;
	out << root->value << '\n';
	inverseTraverse(root->leftChild, out, depth);
}
template <typename T>
binaryTree<T>* binaryTree<T>::huffmanTree(T* chGroup, int n) {
	Node<T>* gNode = new Node<T>[n];
	for (int i = 0; i < n; i++) {
		gNode[i].value = chGroup[i];
		gNode[i].leftChild = nullptr;
		gNode[i].rightChild = nullptr;
	}
	minHeap<Node<T>> heap(n);
	heap.initialize(gNode, n);
	binaryTree<T>* z = new binaryTree<T>;
	Node<T>* w;
	Node<T>* x = new Node<T>();
	Node<T>* y = new Node<T>();
	while(heap.size != 1){
		heap.pop(*x);
	//	*y = heap.top();
		heap.pop(*y);
		w = new Node<T>(x->value + y->value, x, y);
		heap.push(*w);
		x = new Node<T>();
		y = new Node<T>();
		z->setRoot(w);
	}
	return z;
}
template <typename T>
class hNode {
public:
	template <typename T>
	friend class binaryTree;
	hNode();
	hNode(T value);
	hNode(T value, hNode<T>* left, hNode<T>* right);
	int getWeight(){return this->weight;}
	void setLeft(hNode<T>* left);
	void setRight(hNode<T>* right);
	~hNode();
	template <typename T>
	friend bool operator>(hNode<T>& a, hNode<T>& b);
	template <typename T>
	friend bool operator<(hNode<T>& a, hNode<T>& b);
	template <typename T>
	friend bool operator<=(hNode<T>& a, hNode<T>& b);
private:
	int weight;
	binaryTree<int>* tree;
	hNode<T>* leftChild;
	hNode<T>* rightChild;
};
template <typename T>
hNode<T>::hNode(T value) {
	this->weight = value;
	tree = nullptr;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
hNode<T>::hNode() {
	this->weight = 0;
	tree = nullptr;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
hNode<T>::~hNode() {

}
template <typename T>
hNode<T>::hNode(T value, hNode<T>* left, hNode<T>* right) {
	this->weight = value;
	tree = nullptr;
	leftChild = left;
	rightChild = right;
}
template <typename T>
void hNode<T>::setLeft(hNode<T>* left) {
	leftChild = left;
}
template <typename T>
void hNode<T>::setRight(hNode<T>* right) {
	rightChild = right;
}
template <typename T>
bool operator>(hNode<T>& a, hNode<T>& b){
	if (a.weight > b.weight)
		return true;
	else
		return false;
}
template <typename T>
bool operator<(hNode<T>& a, hNode<T>& b) {
	if (a.weight < b.weight)
		return true;
	else
		return false;
}
template <typename T>
bool operator<=(hNode<T>& a, hNode<T>& b) {
	if (a.weight <= b.weight)
		return true;
	else
		return false;
}

